import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:27.移除元素
 * Date: 2024-02-10
 * Time:12:00
 */
public class Solution {

    public int removeElement(int[] nums, int val) {
/*
        //遇到等于val的元素，就往后找不等于val的a，然后让a把那个元素给覆盖掉
        //遇到某个数字val，就标记出来
        int len = nums.length;
        if(len == 0)
            return 0;
        if(len == 1) {
            if(nums[0] != val) {
                return 1;
            } else {
                return 0;
            }
        }

        int left = 0,right = len-1;  //双指针
        int count = 0;  //计数器，每移除一个元素count就加1，最终新数组长度就是len-count
        while(left < right) {
            while(left < len && left < right && nums[left] != val) {
                ++left;
            }
            //此时left指向的元素为val
            while(right >= 0 && left < right && nums[right] ==val) {
                --right;
            }
            nums[left] = nums[right];
            ++left;
            --right;
            ++count;
        }
        return left;
*/

        //思路一
/*
        int len = nums.length;
        int count = 0;
        int[] tmp = new int[len];
        int fast = 0,slow = 0;
        for(int i = 0;i < len;i++) {
            if(nums[i] != val) {
                tmp[slow++] = nums[i];
                count++;
            }
        }
        for(int i = 0;i < count;i++) {
            nums[i] = tmp[i];
        }
        return count;
*/
        //思路二
        int slow = 0;
        for(int fast = 0;fast < nums.length;fast++) {
            if(nums[fast] != val)
                nums[slow++] = nums[fast];
        }
        return slow;
    }
////////////////////////////////////////////////////////
    //求左叶子的和
    public int sumOfLeftLeaves(TreeNode root) {
/*
        //找左叶子  标记cur和parent  前序遍历  判断是否满足cur==parent.left
        TreeNode parent = null;
        int ret = traversal(root,parent);
        return ret;
    }

    private int traversal(TreeNode root,TreeNode parent) {
        int sum = 0;
        if(root == null)
            return 0;
        if(root.left == null && root.right == null) {
            if(root == parent.left)
                return root.val;
            else
                return 0;
        }

        if(root.left != null) {
            parent = root;
            sum += traversal(root.left,parent);
        }
        if(root.right != null) {
            parent = root;
            traversal(root.right,parent);
        }
        return sum;
*/
        if(root == null)
            return 0;
        if(root.left != null && root.left.left == null && root.left.right == null)
            return 0;
        return 0;
    }

//////////////////////////////////////////////////////////////////////////
    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }


    Node pre = null;
    Node head = null;
    public Node treeToDoublyList(Node root) {
        if(root == null)
            return null;
        Node cur = root;
        travelsal(cur);
        head.left = pre;
        pre.right = head;
        return head;
    }

    //中序
    private void travelsal(Node root) {
        if(root == null)
            return;
        travelsal(root.left);
        if(pre == null) {  //遍历到最左边的节点，即链表头节点
            head = root;
            pre = root;
        }
        else {
            pre.right = root;
            root.left = pre;
            pre = root;
        }
        travelsal(root.right);
    }
}
